"""
https://leetcode.cn/problems/minimum-window-substring/description/

76. 最小覆盖子串
困难
相关标签
premium lock icon
相关企业
提示
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

 

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
 

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
 

提示：

m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成
 

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

"""

class Solution:
    """
    滑动窗口统计类。
    难点在于如何统计新来的数和要删除的数

    先统计需要收集的字符及对应数量。

    考虑分别使用一个dict存储窗口内字符对应的数量和位置，
    同时维护一个数组，从小到大统计字符对应的数组。

    遇到一个满足要求的字符时，条件集合、dict、数组均进行维护。
    顺序：条件集合->数组->dict

    遇到需要删除的数组时，依次取消原来的数据。
    顺序：条件集合（允许负数）->dict->数组


    何时更新left？
    
    

    """
    def minWindow(self, s: str, t: str) -> str:
        # 如果条件字符串长度大于内容字符串，则返回空字符串
        if len(t)>len(s):
            return ''
        
        # 收集条件集
        cond={}
        for c in t:
            if c in cond:
                cond[c]+=1
            else:
                cond[c]=1
        csiz=len(cond)

        # 初始化其他集合(pos可用双向队列实现)
        dic={}
        pos=[]


        # 窗口遍历(左右皆包)
        res_range=[]
        min_size=len(s)+1
        left=-1
        for right in range(len(s)):
            c=s[right]
            # 仅处理条件内的字符。条件外的字符直接忽略
            if c not in cond:
                continue
            # 初始化left
            if left==-1:
                left=right
            # 添加字符逻辑（任何情况，遇到就添加维护）
            cond[c]-=1
            pos.append(right)
            # 维护完整子串的数字
            if cond[c]==0:
                csiz-=1
            
            if csiz==0:
                cur_size=right-left+1
                if cur_size<min_size:
                    min_size=cur_size
                    res_range.append(s[left:right+1])

            # 删除字符（如果已经构建了完整子串，且pos中最靠前的字符，与当前字符相同，则尝试删除）
            # 注：以下行为必定始终需要在维护完整子串的情况下执行
            if csiz==0 and pos[0]!=right:
                move_left=False
                while cond[s[pos[0]]]<0:
                    cond[s[pos[0]]]+=1
                    pos.pop(0)
                    move_left=True
                if not move_left:
                    continue
                left=pos[0]
                cur_size=right-left+1
                if cur_size<min_size:
                    min_size=cur_size
                    res_range.append(s[left:right+1])

            # 如果min_size=len(t)，不可能更小了，则直接返回
            if min_size==len(t):
                break
        if res_range:
            return res_range[-1]
        else:
            return ""


if __name__=='__main__':
    s='bba'
    t='ab'

    res=Solution().minWindow(s,t)
    print(res)

    pass